package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Description:
 * 5. 最长回文子串
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 *
 * @author weiruibai.vendor
 * Date: 2022/2/19 10:12
 */
public class Solution_longestPalindrome_5 {

    public static void main(String[] args) {
        String s = "babad";
        //s = "abcdefffe";
        //s = "ac";
        s = "abcabfbaczbaee";
        s = "cbbd";
        System.out.println(longestPalindrome(s));
    }

    /**
     * 非递归方法
     * 1、计算每个字符的下标位置map<char,List<Integer>>
     * 2、遍历每个字符，计算这个区间是否是回文，取最长
     * eg: s="abcabfbaczbaee"
     * 可以划分如下
     * 1、a字符为首尾节点
     * abca
     * abcabfba
     * abcabfbaczba
     * 2、b字符为首尾节点
     * bcab
     * bcabfb
     * bcabfbaczb
     * 3、f字符为首尾节点
     * f --出现一次，那么可以由此向两边扩展，直到不相等就停止
     * 4、c字符为首尾节点
     * cabfbac
     * 5、z字符为首尾节点
     * z
     * 6、e字符为首尾节点
     * ee
     * 然后遍历以上各个字符串，两边向中间收缩看是否是回文
     * 返回最长的
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        char[] chars = s.toCharArray();
        Map<Character, List<Integer>> characterListMap = eachCharIndex(chars);
        String result = "";
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < chars.length; i++) {
            if (set.add(chars[i])) {
                List<Integer> list = characterListMap.get(chars[i]);
                for (int j = 0; j < list.size(); j++) {
                    if (list.size() == 1) {
                        /**
                         * 当这个字符只出现一次，就根据这个字符的位置两边扩展
                         */
                        int[] arr = build(chars, list.get(j));
                        if (arr != null && (arr[1] - arr[0] + 1) > result.length()) {
                            result = s.substring(arr[0], arr[1] + 1);
                        }
                    } else {
                        /**
                         * 字符出现两次或两次以上，就计算这个区间的字符是否是回文
                         */
                        int L = list.get(j);
                        for (int K = j + 1; K < list.size(); K++) {
                            int R = list.get(K);
                            boolean isHave = process_1(chars, L, R);
                            if (isHave && (R + 1 - L) > result.length()) {
                                result = s.substring(L, R + 1);
                            }
                        }
                    }
                }

            }
        }
        return result;
    }

    /**
     * @param chars
     * @param middelIndex
     * @return
     */
    private static int[] build(char[] chars, Integer middelIndex) {
        if (middelIndex == 0 || middelIndex == chars.length - 1) {
            return new int[]{middelIndex, middelIndex};
        }
        return outBuildProcess(chars, middelIndex - 1, middelIndex + 1);
    }

    private static int[] outBuildProcess(char[] chars, int L, int R) {
        if (L < 0 || R >= chars.length || chars[L] != chars[R]) {
            return new int[]{L + 1, R - 1};
        }
        return outBuildProcess(chars, L - 1, R + 1);
    }

    /**
     * 计算每个字符的起始位置并返回
     *
     * @param chars
     * @return
     */
    static Map<Character, List<Integer>> eachCharIndex(char[] chars) {
        Map<Character, List<Integer>> eachCharIndex = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            if (!eachCharIndex.containsKey(chars[i])) {
                int finalI = i;
                eachCharIndex.put(chars[i], new ArrayList<Integer>() {{
                    add(finalI);
                }});
            } else {
                eachCharIndex.get(chars[i]).add(i);
            }
        }
        return eachCharIndex;
    }

    /**
     * 根据字符的始末位置，计算是否是回文（错）
     *
     * @param characters
     * @param L          同一个字符的开始节点
     * @param R          同一个字符的末尾节点
     * @return
     */
    private static boolean process_1(char[] characters, int L, int R) {
        if (L >= R) {
            return true;
        }
        if (characters[L] != characters[R]) {
            // 只要出现不想等，就不是回文
            return false;
        }
        return process_1(characters, L + 1, R - 1);
    }


}
